
#if !defined(_KERNEL) && !defined(_STANDALONE)
#include <limits.h>
#include <stdint.h>
#include <strings.h>
#else
#include <lib/libkern/libkern.h>
#include <machine/limits.h>
#endif

#ifndef popcount32	// might be a builtin

/*
 * This a hybrid algorithm for bit counting between parallel counting and
 * using multiplication.  The idea is to sum up the bits in each Byte, so
 * that the final accumulation can be done with a single multiplication.
 * If the platform has a slow multiplication instruction, it can be replaced
 * by the commented out version below.
 */

unsigned int
popcount32(uint32_t v)
{
	unsigned int c;

	v = v - ((v >> 1) & 0x55555555U);
	v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
	v = (v + (v >> 4)) & 0x0f0f0f0fU;
	c = (v * 0x01010101U) >> 24;
	/*
	 * v = (v >> 16) + v;
	 * v = (v >> 8) + v;
	 * c = v & 255;
	 */

	return c;
}

#if UINT_MAX == 0xffffffffU
__strong_alias(popcount, popcount32)
#endif

#if ULONG_MAX == 0xffffffffU
__strong_alias(popcountl, popcount32)
#endif

#endif	/* !popcount32 */
